#ifndef LEVENSHTEINDISTANCE_HPP
#define LEVENSHTEINDISTANCE_HPP

#include <string>
#include <vector>
#include <iostream>

class LevenshteinDistance
{
public:
    LevenshteinDistance();
    virtual int distance(const std::string &s1, const std::string &s2);

protected:
    template<class T>
    T min(const std::vector<T> tab)
    {
        T min = tab[0];
        for(int i =0; i< tab.size();i++)
        {
            if(min > tab[i]) min = tab[i];
        }
        return min;
    }

    template<class T>
    T min(const T& a,const T& b, const T& c)
    {
        /*std::vector<T> tab;
        tab.push_back(a);
        tab.push_back(b);
        tab.push_back(c);
        T t= min(tab);*/
        if(a<b){
            if(a<c) return a;
            else return b;
        }
        else{
            if(b<c) return b;
            else return c;
        }

    }
    template <class T> unsigned int edit_distance(const T& s1, const T& s2)
    {
        const size_t len1 = s1.size(), len2 = s2.size();
        std::vector<std::vector<unsigned int> > d(len1 + 1, std::vector<unsigned int>(len2 + 1));

        d[0][0] = 0;
        for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i;
        for(unsigned int i = 1; i <= len2; ++i) d[0][i] = i;

        for(unsigned int i = 1; i <= len1; ++i){
            for(unsigned int j = 1; j <= len2; ++j){
                d[i][j] = std::min(
                        std::min(d[i - 1][j] + 1,d[i][j - 1] + 1),
                        d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1) );

               /* if(i==j){
                    std::cout << i << " " << j << std::endl;
                    if(d[i][j] == d[i - 1][j] + 1)
                        std::cout << "insertion" << std::endl;
                    if(d[i][j] == d[i][j-1] + 1)
                        std::cout << "supression" << std::endl;
                    if( d[i][j] == d[i - 1][j - 1] +1)
                        std::cout << "substituion" << std::endl;
                }*/
            }
        }
        return d[len1][len2];
    }

};

#endif // LEVENSHTEINDISTANCE_HPP
